import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class Main {
    //统计好整数的数目
    public long countGoodIntegers(int n, int k) {
        int start = 0;
        int end = 0;
        String startStr = "1";
        String endStr = "9";
        for(int i=1;i<n;i++){
            startStr += "0";
            endStr += "9";
        }
        start = Integer.parseInt(startStr);
        end = Integer.parseInt(endStr);
        long all = 0;
        long change = 0;
        for(int j=start;j<=end;j++){
            Set<List<Integer>> set = new HashSet<>();
            if(j%k==0){
                Map<Integer,Integer> map = new HashMap<>();
                String str = j+"";
                long sum = 1;
                long sum0 = 0;
                int[] visited = new int[n];
                for(int i=0;i<n;i++){
                    /*统计所有的排列顺序*/
                    sum = sum*(1+i);
                    /*细分数据数量*/
                    int num = str.charAt(i)-'0';
                    visited[i] = num;/*记忆化*/
                    if(map.containsKey(num)){
                        map.put(num,map.get(num)+1);
                    }
                    else{
                        map.put(num,1);
                    }
                }
                if(!set.add(arrayToList(visited))) continue;
                sum0 = sum/n;/*考虑0开头*/
                // 打印 Map 的内容
                int ans = 0;/*记录奇数的个数 例如[3,2,3,2,3],[1,2,3,2,1]只能有一个奇数,偶数不限设*/
                long need = 1;
                /*所有情况（包括前置0）*/
                for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                    if(entry.getValue()%2!=0){
                        ans++;
                    }
                    long mid = 1;
                    for(int i=1;i<=entry.getValue();i++) mid=mid*i;
                    need = need*mid;
                }
                if(ans>1) continue;
                sum = sum / need;/*all*/
                /*删除前置0（如果有key为0）*/
                if(map.containsKey(0)){
                    long need2 = 1;
                    map.put(0,map.get(0)-1);
                    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                        if(entry.getValue()==0){
                            continue;/*当只有一个0的情况发生*/
                        }
                        long mid = 1;
                        for(int i=1;i<=entry.getValue();i++) mid=mid*i;
                        need2 = need2*mid;
                    }
                    sum = sum - (sum0 / need2);
                    change = sum;
                }
            }
            all = all + change;
        }
        return all;
    }

    // 将数组转换为 List
    public static List<Integer> arrayToList(int[] array) {
        List<Integer> list = new ArrayList<>();
        for (int num : array) {
            list.add(num);
        }
        return list;
    }
}
